package _01_第一季.堆08;

import _01_第一季._00_公共接口.Heap;

import java.util.Comparator;

public class BinaryHeap<E> implements Heap<E> {
    private int size;
    private E[] elements;
    private Comparator<E> comparator;
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(E[] elements){
        this(elements,null);
    }

    //外界传进来一个数组，对它进行批量建堆
    public BinaryHeap(E[] elements,Comparator<E> comparator){
        this.comparator = comparator;
        if(elements == null || elements.length == 0){
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        }else{
            size = elements.length;
            int capacity = Math.max(elements.length,DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for(int i=0;i< elements.length;++i){
                this.elements[i] = elements[i];
            }
            heapify(); //开始批量建堆
        }
    }

    private void heapify() {
        //自下而上的下滤
        for(int i=(size >> 1)-1;i>=0;i--){
            siftDown(i);
        }
    }

    public BinaryHeap(){
        this(null,null);
    }

    public BinaryHeap(Comparator<E> comparator){
        this(null,comparator);
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 检查堆是否为空
     */
    private void emptyCheck(){
        if(size == 0){
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    /**
     * 检测传入的元素是否为空，元素必须具备可比较性，所以不能为空
     * @param element
     */
    private void elementNotNullCheck(E element){
        if(element == null){
            throw new IllegalArgumentException("element must not be null");
        }
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    //添加
    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size+1);
        elements[size++] = element;
        siftUp(size-1);
    }

    //上滤
    private void siftUp(int index) {
       E element = elements[index];
       while(index>0){
           int parentIndex = (index-1)>>1;
           E parentElement = elements[parentIndex];
           if(compare(element,parentElement)<=0) break;

           elements[index] = parentElement;
           index = parentIndex;
       }
       elements[index] = element;
    }

    //获取堆顶元素,获取最大值
    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    //删除堆顶元素并返回
    @Override
    public E remove() {
        emptyCheck();
        int lastIndex = --size;
        E ret = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        siftDown(0);
        return ret;
    }

    //下滤操作
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        while(index<half){
            int leftChildIndex = (index<<1)+1;
            E leftChildElement = elements[leftChildIndex];

            int rightChildIndex = leftChildIndex+1;
            if(rightChildIndex<size && compare(leftChildElement,elements[rightChildIndex])<0){
                leftChildElement = elements[leftChildIndex = rightChildIndex];
            }
            if(compare(element,leftChildElement)>=0) break;

            elements[index] = leftChildElement;
            index = leftChildIndex;
        }
        elements[index] = element;
    }

    //删除堆顶元素并返回堆顶元素，并新增一个元素
    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root = null;
        if(size == 0){
            elements[0] = element;
            size++;
        }else{
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

    //扩容方法
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if(capacity <= oldCapacity) return;

        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];

        for(int i=0;i<size;++i){
            newElements[i] = elements[i];
        }

        elements = newElements;

        System.out.println(oldCapacity+"扩容为:"+newCapacity);
    }

    private int compare(E e1,E e2){
        return comparator != null ? comparator.compare(e1,e2) : ((Comparable<E>)e1).compareTo(e2);
    }
}
